package www.study.com;

//通配符匹配 https://leetcode.cn/problems/wildcard-matching/
//详见二哥
public class code44 {
    public static void main(String[] args) {

    }

    class Solution {
        public boolean isMatch(String s, String p) {
            boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
            dp[0][0] = true; //设定从下标1处开始 0位置代表空串
            for(int j = 0 ; j < p.length() ; j++){
                if(p.charAt(j) == '*'){
                    dp[0][j + 1] = true;
                }else{
                    break;
                }
            }
            for(int i = 1 ; i <= s.length() ; i++){
                for(int j = 1 ; j <= p.length() ; j++){
                    if(p.charAt(j - 1) == '*'){
                        dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
                    }else{
                        if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'){
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }
                }
            }
            return dp[s.length()][p.length()];
        }
    }
}
